﻿#define  _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include <vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

//int main(void)
//{
//	vector<int>array;
//	array.push_back(100);
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(300);
//
//	array.push_back(500);
//
//	vector<int>::iterator itor;
//
//	for (itor = array.begin(); itor != array.end(); itor++)
//
//	{
//
//		if (*itor == 300)
//
//		{
//
//			itor = array.erase(itor);
//
//		}
//
//	}
//
//	for (itor = array.begin(); itor != array.end(); itor++)
//
//	{
//
//		cout << *itor << " ";
//
//	}
//
//	return 0;
//
//}

//int main()
//{
//	int ar[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int n = sizeof(ar) / sizeof(int);
//	vector<int> v(ar, ar + n);
//	cout << v.size() << ":" << v.capacity() << endl;
//	v.reserve(100);
//	v.resize(20);
//	cout << v.size() << ":" << v.capacity() << endl;
//	v.reserve(50);
//	v.resize(5);
//	cout << v.size() << ":" << v.capacity() << endl;
//}

//136. 只出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            ans ^= nums[i];
        }
        return ans;
    }
};

//118. 杨辉三角
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv(numRows);
        for (int i = 0; i < numRows; ++i)
        {
            vv[i].resize(i + 1, 1);
        }

        for (int i = 2; i < numRows; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
            }
        }

        return vv;
    }
};

//260. 只出现一次的数字 III
//位运算
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int res = 0;
        vector<int> vi(2);
        for (auto ch : nums)
        {
            res ^= ch;
        }
        //防止溢出
        int ans = (res == INT_MIN ? res : res & (-res));
        //通过最后一位为1，将数字分成两类
        int i = 0;
        for (auto num : nums)
        {
            if (ans & num)
            {
                vi[0] ^= num;
            }
            else
            {
                vi[1] ^= num;
            }
        }
        return vi;
    }
};

//17. 电话号码的字母组合(全排列)
class Solution {
    string _numStr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    void Combinations(const string& digits, size_t di, string combineStr, vector<string>& strV)
    {
        if (di == digits.size())
        {
            strV.push_back(combineStr);
            return;
        }
        int num = digits[di] - '0';
        string str = _numStr[num];
        for (auto ch : str)
        {
            Combinations(digits, di + 1, combineStr + ch, strV);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> strV;
        if (digits.size() == 0)
        {
            return strV;
        }
        Combinations(digits, 0, "", strV);
        return strV;
    }
};


//137. 只出现一次的数字 II

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if (nums.size() == 1)
        {
            return nums[0];
        }
        sort(nums.begin(), nums.end());

        if (nums[0] != nums[1])
        {
            return nums[0];
        }

        for (int i = 1; i < nums.size() - 1; i++)
        {
            if (nums[i] != nums[i + 1] && nums[i] != nums[i - 1])
            {
                return nums[i];
            }
        }

        return nums[nums.size() - 1];
    }
};


//哈希表
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        unordered_map<int, int> frep;
//        for (auto ch : nums)
//        {
//            frep[ch]++;
//        }
//
//        int ans = 0;
//        for (auto [num, occ] : frep)
//        {
//            if (occ == 1)
//            {
//                ans = num;
//                break;
//            }
//        }
//        return ans;
//    }
//};


//26. 删除有序数组中的重复项(双指针)
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int cur = 0, dest = 0;
        while (cur < nums.size())
        {
            if (nums[cur] == nums[dest])
            {
                ++cur;
            }
            else
            {
                ++dest;
                nums[dest] = nums[cur];
                ++cur;
            }
        }
        return dest + 1;
    }
};